package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-11 19:03
 */

import java.util.HashMap;

/**
 * 题目：
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
 * <p>
 * 注意：这里是整数数组，所以无法用滑块窗口的方法解决
 * <p>
 * 思路：前缀和法
 * map存放 数组和 以及 出现的次数
 * 每次遍历检查是否存在key=数组和 - k
 * 若是存在说明存在 某点到 到i处和为k
 */

public class Test22_和为K的子数组 {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int pre_sum = 0;
        int ret = 0;
        //若数组nums[0]就满足条件，但是map中还没有前缀和，所以插入默认的map.(0,1)
        map.put(0, 1);

        for (int i : nums) {
            pre_sum += i;
            if (map.containsKey(pre_sum - k)) {
                ret += map.get(pre_sum - k);
            }
            map.put(pre_sum, map.getOrDefault(pre_sum, 0) + 1);

        }
        return ret;
    }
}
